#include <iostream>
#include <list>
#include <utility>
#include <unordered_map>

using std::cout;
using std::endl;
using std::list;
using std::pair;
using std::unordered_map;

class LRU
{
public:
    LRU(int capa)
    : _capacity(capa)
    {

    }

    void put(int key, int value)
    {
        auto it = _cache.find(key);
        //key不在list中，也不在um中，表明是一个新key
        if(it == _cache.end())
        {
            //判断list是不是满的
            if(_capacity == (int)_nodes.size())
            {
                auto deleteNode = _nodes.back();
                //最后一个元素从list中删除
                _nodes.pop_back();
                //从um中删除
                /* auto it2 = _cache.find(deleteNode.first); */
                /* _cache.erase(it2); */
                _cache.erase(_cache.find(deleteNode.first));

            }
            //将key，value插入到list的头部
            _nodes.push_front({key, value});
            //以及更新到um中
            _cache[key] = _nodes.begin(); 

        }
        else
        {
            //有可能key值是一样的，但是value值不一样，所以
            //value值需要更新
            it->second->second = value;
            _nodes.splice(_nodes.begin(), _nodes, it->second);
        }
    }

    int get(int key)
    {
        auto it = _cache.find(key);
        if(it == _cache.end())
        {
            return -1;
        }
        else
        {
            //在读的时候，发现key是存在的，也需要更新到list的最前面
            _nodes.splice(_nodes.begin(), _nodes, it->second);
            return it->second->second;
        }
    }

    void print()
    {
        for(auto &elem : _nodes)
        {
            cout << "(" << elem.first
                 << ", " << elem.second
                 << ") ";
        }
        cout << endl;
    }
private:
    int _capacity;//容量的大小
    list<pair<int, int>> _nodes;//存放元素
    unordered_map<int, list<pair<int, int>>::iterator> _cache;//key与key在list中的迭代器的位置
};

void test()
{
    LRU lru(3);
    lru.put(1, 10);
    lru.print();

    cout << endl;
    lru.put(2, 20);
    lru.print();

    cout << endl;
    cout << "lru.get(1) = " << lru.get(1) << endl;
    lru.print();

    cout << endl;
    lru.put(3, 30);
    lru.print();

    cout << endl;
    lru.put(4, 40);
    lru.print();

    cout << endl;
    lru.put(3, 300);
    lru.print();

    cout << endl;
    cout << "lru.get(1) = " << lru.get(1) << endl;
    lru.print();

    cout << endl;
    cout << "lru.get(2) = " << lru.get(2) << endl;
    lru.print();
}

int main(int argc, char *argv[])
{
    test();
    return 0;
}

